package org.mmtk.plan.scale.colors;

import org.mmtk.plan.scale.ScaleTraceLocal;
import org.mmtk.plan.scale.utils.ArayHelper;
import org.mmtk.plan.scale.utils.ScaleLogger;
import org.mmtk.policy.Space;
import org.mmtk.utility.Log;
import org.mmtk.utility.deque.ObjectReferenceDeque;
import org.mmtk.utility.options.Options;
import org.mmtk.vm.Lock;
import org.mmtk.vm.VM;
import org.vmmagic.pragma.Interruptible;
import org.vmmagic.pragma.Uninterruptible;
import org.vmmagic.unboxed.Address;
import org.vmmagic.unboxed.ObjectReference;
import org.vmmagic.unboxed.ObjectReferenceArray;

/**
 * This class is responsible to hold the global color table and synchronize access to it.
 * Class instances represent specific colors with their properties and methods.
 * 
 * Index into the colors table is the value of the color mark - that's why we do not use index=0;
 * Object with color mark zero is unmarked object.
 * 
 * @author kathy
 */
@Uninterruptible
class Color {
	private final static int SAVE_OTHER_SPACE = 50;
	/**
	 * Static fields and methods
	 */
	private static final Lock colorsTableLock;	
	//color table
	public static ObjectReference tableRef;
	private static Color[] colorsTable;
	private static int colorsTableSize;
	private static int colorsTableIndex;
	
	//trace completion
	private static int traceCompletionIndex;
	private static boolean inTraceComplete;
	private static int colorTableTraces;
	
	//parameters
	private static int maxObjectsToColor;

	static {
		colorsTableLock = VM.newLock("colorsTableLock");			
	}
	
	/**
	 * Called upon plan initialization when parameters are set
	 */
	@Interruptible
	static void init() {
		if(SColors.getHelperColors() == 0) {
			//no colors needed
			colorsTableSize = 0;
			return;
		}
		maxObjectsToColor = Options.scMaxColor.getValue();
		colorsTableSize = SColors.getHelperColors() + 1;
		colorsTable = new Color[colorsTableSize];
		for (int i = 1; i < colorsTableSize; i++) {
			colorsTable[i] = new Color(i);
		}
		tableRef = ObjectReference.fromObject(colorsTable);
		Log.write("Color initialized, maxObjectsToColor=");
		Log.writeln(maxObjectsToColor);
		Log.flush();
	}
	private static void acquireColorsTableLock() {
		if(Options.scaleDebug.getValue() > 4) {
			ScaleLogger.acquireLogLock();
			Log.prependThreadId();
			Log.writeln("Trying to acquire colorsTableLock");
			Log.flush();
			ScaleLogger.releaseLogLock();
		}
		colorsTableLock.acquire();
		if(Options.scaleDebug.getValue() > 4) {
			ScaleLogger.acquireLogLock();
			Log.prependThreadId();
			Log.writeln("Acquired colorsTableLock");
			Log.flush();
			ScaleLogger.releaseLogLock();
		}
	}
	private static void releaseColorsTableLock() {
		colorsTableLock.release();
		if(Options.scaleDebug.getValue() > 4) {
			ScaleLogger.acquireLogLock();
			Log.prependThreadId();
			Log.writeln("Released colorsTableLock");
			Log.flush();
			ScaleLogger.releaseLogLock();
		}
	}
	
	private static int getColorsTableEnd() {
		int end;
		
		if(colorsTableIndex < colorsTableSize) {
			end = colorsTableIndex+1;
		} else {
			end = colorsTableSize;
		}
		
		return end;
	}

	/**
	 * Called upon GC cycle start - to clean up previous cycle data
	 */
	static void prepareColorsTable() {
		if(colorsTableSize == 0) {
			//no colors in this run
			return;
		}
		
		int end = getColorsTableEnd();
		for (int i = 1; i < end; i++) {
			colorsTable[i].prepare();
		}
		colorsTableIndex = 0;
		traceCompletionIndex = 0;
		inTraceComplete = false;
		colorTableTraces = 0;
	}
	
	/**
	 * Called by helpers when they need to start coloring on the new color
	 * @return
	 */
	static Color obtainColor() {
		Color result = null;
		
		if(Options.scaleDebug.getValue() > 5) {
			ScaleLogger.acquireLogLock();
			Log.prependThreadId();
			Log.write("Color.obtainColor - enter, colorTableIndex=");
			Log.writeln(colorsTableIndex);
			Log.flush();
			ScaleLogger.releaseLogLock();
		}
		
		if(colorsTableIndex == colorsTableSize) {
			return result;
		}
		
		acquireColorsTableLock();
		if(Options.scaleDebug.getValue() > 5) {
			Log.prependThreadId();
			Log.write("Color.obtainColor - in lock, colorTableIndex=");
			Log.writeln(colorsTableIndex);
			Log.flush();
		}
		if(colorsTableIndex < colorsTableSize) {
			colorsTableIndex++;
			if(colorsTableIndex < colorsTableSize) {
				result = colorsTable[colorsTableIndex];
			}
		}
		releaseColorsTableLock();
			
		if(result != null && Options.scaleDebug.getValue() > 5) {
			ScaleLogger.acquireLogLock();
			Log.prependThreadId();
			Log.write("Color.obtainColor - exit, result=");
			Log.writeln(result.index);
			Log.flush();
			ScaleLogger.releaseLogLock();
		}
		return result;
	}
	
	/**
	 * Called while tracing through abandoned fronts
	 * @return
	 */
	static Color obtainColorToComplete() {
		Color result = null;
		Color color;
		
		int end = getColorsTableEnd();
		
		acquireColorsTableLock();	
		if(!inTraceComplete) {
			inTraceComplete = true;
		}
		
		if(traceCompletionIndex >= end) {
			//if(traceCompleteDone) {
			//	releaseColorsTableLock();
			//	return result;
			//}
			if(Options.scaleDebug.getValue() > 3) {
				ScaleLogger.acquireLogLock();
				Log.prependThreadId();
				Log.writeln("\tColor.obtainColorToComplete starting new round");
				Log.flush();
				ScaleLogger.releaseLogLock();
			}
			//checkColorsTable();
			traceCompletionIndex = 0;
		}
		while(traceCompletionIndex < end) {
			traceCompletionIndex++;
			if(traceCompletionIndex < end) {
				color = colorsTable[traceCompletionIndex];
				if(color.live && color.numSavedValues > 0 && !color.savedValuesTraced) {
					result = color;
					color.savedValuesTraced = true;
					break;
				}
			}
		}
		releaseColorsTableLock();
			
		if(result != null && Options.scaleDebug.getValue() > 3) {
			ScaleLogger.acquireLogLock();
			Log.prependThreadId(); 
			Log.write(" Color.obtainColorToComplete - exit, result=");
			Log.writeln(result.index);
			ScaleLogger.releaseLogLock();
		}
		return result;
	}
	
	/**
	 * Called when getting abandoned fronts before checking trace
	 * //TODO - change this !!!!
	 * @param traceLocal
	 * @return
	 */
	public static long getAllSavedValues(ScaleTraceLocal traceLocal) {
		Color color;
		int numSavedValues;
		ObjectReferenceArray savedValues;
		ObjectReference objRef;
		int i;
		int j;
		long total = 0;
		int end = getColorsTableEnd();
		for (i = 1; i < end; i++) {
			color = colorsTable[i];
			numSavedValues = color.numSavedValues;
			if(color.live && numSavedValues > 0) {
				savedValues = color.savedValues;
				for(j = 0; j < numSavedValues; j++) {
					objRef = savedValues.get(j);
					traceLocal.processNode(objRef);
					total++;
				}
				color.numSavedValues = 0;
			}
		}
		
		return total;
	}

	static Color getColor(ObjectReference colorMark) {
		if (Options.scaleDebug.getValue() > 9) {
			ScaleLogger.acquireLogLock();
			Log.prependThreadId();
			Log.write(" Color.getColor(9), colorMark=");
			Log.writeln(colorMark);
			Log.flush();
			ScaleLogger.releaseLogLock();
		}
		int colorIndex = colorMark.toAddress().toInt();
		return getColor(colorIndex);
	}

	static Color getColor(int colorIndex) {
		Color result = null;
		if (Options.scaleDebug.getValue() > 9) {
			ScaleLogger.acquireLogLock();
			Log.prependThreadId();
			Log.write(" Color.getColor(9), colorIndex=");
			Log.write(colorIndex);
			Log.write(", colorTableIndex=");
			Log.write(colorsTableIndex);
			Log.flush();
			ScaleLogger.releaseLogLock();
		}
		if (colorIndex > 0 && colorIndex <= colorsTableIndex) {
			result = colorsTable[colorIndex];
		}
		if (Options.scaleDebug.getValue() > 9) {
			ScaleLogger.acquireLogLock();
			Log.write(", result=");
			if (result != null) {
				result.dump();
			} else {
				Log.write("null\n");
			}
			Log.flush();
			ScaleLogger.releaseLogLock();
		}
		return result;
	}

	static boolean traceLiveColor(int colorIndex) {
		boolean result = false;
		Color color = colorsTable[colorIndex];
		int end = getColorsTableEnd();
		for (int j = 1; j < end; j++) {
			if (j == colorIndex) {
				continue;
			}
			if (!color.otherColors[j]) {
				continue;
			}
			if (colorsTable[j].markLive()) {
				if (Options.scaleDebug.getValue() > 3) {
					ScaleLogger.acquireLogLock();
					Log.prependThreadId();
					Log.write(" Color.traceLiveColor - dead color turned live, i=");
					Log.write(colorIndex);
					Log.write(", j=");
					Log.writeln(j);
					Log.flush();
					ScaleLogger.releaseLogLock();
				}
				if(!result) {
					result=true;
				}
			}
		}
		
		return result;
	}
	
	//single threaded
	static boolean checkColorsTable(boolean all) {
		boolean result = false;
		int end = getColorsTableEnd();
		Log.write("Color.checkColorsTable enter, all= ");
		Log.write(all);
		Log.write(", end= ");
		Log.writeln(end);
		Log.flush();
		for (int i = 1; i < end; i++) {		
			Color color = colorsTable[i];
			if (!color.isLive() && color.liveColored > 0 ) {
				if(all || color.numSavedValues > 0 || color.otherColors() > 0) {
					//this is to fix possible bug related to tracing other space objects
					Log.write("Color.checkColorsTable - !!! dirty trick ");
					color.dump();
					color.markLive();
					result = true;
					break;
				}
			}
		}
		return result;
	}
	
	//single threaded
	static boolean traceLiveColors(boolean withCheck) {
		colorTableTraces++;
		boolean result=false;
		if(colorsTableSize == 0) {
			return result;
		}
		boolean done = false;
		int end = getColorsTableEnd() - 1;
		while (!done) {
			done = true;

			for (int i = end; i > 0; i--) {
				
				Color color = colorsTable[i];
				if (!color.isLive()) {
					//if(color.liveColored > 0) {
						//this is to fix possible bug related to tracing other space objects
						//Log.write("Color.traceLiveColors - !!! dirty trick ");
						//color.dump();
						//color.live = true;
					//} else {
						continue;
					//}
				}
				if(traceLiveColor(i)) {
					result = true;
					done = false;
				}
			}
		}
		
		if(!withCheck) {
			return result;
		}
		
		if(!result) {
			if(checkColorsTable(false)) {
				return true;
			} else {
				return checkColorsTable(true);
			}
		}
		return result;
	}

	static void dumpColorsTable(boolean full) {
		if(colorsTableSize == 0) {
			Log.writeln("No colors table");
			return;
		} 
		
		int liveColors = 0;
		int deadColors = 0;
		int liveWithSavedNotTraced = 0;
		
		int totalDeadColoredLive = 0;
		int totalLiveColoredLive = 0;
		int totalDeadColoredDead = 0;
		int totalLiveColoredDead = 0;
		
		int totalSavedDead = 0;
		int totalLostOS = 0;
		
		Log.write("Colors table dump: colorTableIndex=");
		Log.write(colorsTableIndex);
		Log.write(", colorTableTraces=");
		Log.writeln(colorTableTraces);
		int end = getColorsTableEnd();
		for (int i = 1; i < end; i++) {
			Color color = colorsTable[i];
			if(full) {
				color.dump();
			}
			if(color.isLive()) {
				liveColors++;
				if(color.getNumSavedValues() > 0) {
					if(! color.isSavedValuesTraced()){
						liveWithSavedNotTraced++;
					}
				}
				totalDeadColoredLive += color.deadColored;
				totalLiveColoredLive += color.liveColored;
			} else {
				deadColors++;
				totalDeadColoredDead += color.deadColored;
				totalLiveColoredDead += color.liveColored;
			}
			totalSavedDead += color.numSavedDead;
			if(color.numSavedOSObjects > SAVE_OTHER_SPACE) {
				totalLostOS += (color.numSavedOSObjects - SAVE_OTHER_SPACE);
			}
		}
		if(liveWithSavedNotTraced > 0) {
			Log.write("Saved objects not traced !!! ");
			Log.writeln(liveWithSavedNotTraced);
			Log.flush();
		}
		if(totalLostOS > 0) {
			Log.write("Lost OS objects !!! ");
			Log.writeln(totalLostOS);
			Log.flush();
		}
		if(totalLiveColoredDead > 0) {
			Log.write("Live objects colored dead colors !!! ");
			Log.writeln(totalLiveColoredDead);
			Log.flush();
		}
		Log.write("ColorsTableSummary, liveColors: ");
		Log.write(liveColors);
		Log.write(" deadColors: ");
		Log.write(deadColors);
		Log.write(" totalSavedDead: ");
		Log.write(totalSavedDead);
		Log.write(" totalLiveColoredLive: ");
		Log.write(totalLiveColoredLive);
		Log.write(" totalDeadColoredLive: ");
		Log.write(totalDeadColoredLive);
		Log.write(" totalLiveColoredDead: ");
		Log.write(totalLiveColoredDead);
		Log.write(" totalDeadColoredDead: ");
		Log.writeln(totalDeadColoredDead);
	}

	/**
	 * Instance fields and methods
	 */
	private final int index;
	private Address root;
	private long madeLive;
	private long colored;
	private long liveColored;
	private long markedColored;
	private long deadColored;	
	private boolean live;
	private boolean done;
	private boolean savedValuesTraced;
	private boolean[] otherColors;
	private ObjectReferenceArray savedValues;	
	private int numSavedValues;
	private int numSavedDead;
	
	private int numOSObjects;
	private int numSavedOSObjects;
	private ObjectReferenceArray osObjects;
	
	Color(int index) {
		this.index = index;
		this.otherColors = new boolean[colorsTableSize];
		this.savedValues = ObjectReferenceArray.create(maxObjectsToColor*3);
		this.osObjects = ObjectReferenceArray.create(SAVE_OTHER_SPACE);
	}

	void dump() {
		Log.write(this.index);
		if (isLive()) {
			Log.write(" live");
		} else {
			Log.write(" not live");
		}
		Log.write(", done=");
		Log.write(done);	
		Log.write(", savedTraced=");
		Log.write(savedValuesTraced);	
		Log.write(", savedValues=");
		Log.write(numSavedValues);	
		Log.write(", savedDead=");
		Log.write(numSavedDead);
		Log.write(", root=");
		Log.write(root);
		Log.write(", colored=");
		Log.write(colored);
		Log.write(", liveC=");
		Log.write(liveColored);
		Log.write(", markedC=");
		Log.write(markedColored);
		Log.write(", deadC=");
		Log.write(deadColored);
		Log.write(", otherSO=");
		Log.write(numOSObjects);
		Log.write(", savedOS=");
		Log.write(this.numSavedOSObjects);	
		Log.write(", otherC=[");
		boolean first = true;
		int end = getColorsTableEnd();
		for(int i = 1; i < end; i++) {
			if(otherColors[i]) {
				if(!first) {
					Log.write(", ");
				} else {
					first = false;
				}
				Log.write(i);
			}
		}
		Log.write("]\n");
		Log.flush();
	}

	private void prepare() {
		this.root = Address.zero();
		this.madeLive = 0;
		this.colored = 0;
		this.liveColored = 0;
		this.markedColored = 0;
		this.deadColored = 0;
		this.numOSObjects = 0;
		this.live = false;
		this.done = false;
		this.savedValuesTraced = false;
		for(int i = 1; i < colorsTableSize; i++) {
			if(otherColors[i]) {
				otherColors[i] = false;
			}
		}
		ArayHelper.zeroArray(this.savedValues);
		ArayHelper.zeroArray(this.osObjects);
		this.numSavedValues = 0;
		this.numSavedDead = 0;
		this.numSavedOSObjects = 0;
	}

	void saveObjectsFront(ObjectReferenceDeque values) {
		int index = 0;
		int lost = 0;
		int size = savedValues.length();
		int objectMark;
		if (Options.scaleDebug.getValue() > 2) {
			ScaleLogger.acquireLogLock();
			Log.prependThreadId();
			Log.write("saveObjectsFront - enter, numSavedValues=");
			Log.write(numSavedValues);
			Log.write(", size=");
			Log.write(size);
			Log.write(", colored=");
			Log.writeln(colored);
			Log.flush();
			ScaleLogger.releaseLogLock();
		}
		while(!values.isEmpty()) {
			ObjectReference object = values.pop();
			if(index < size) {		
				savedValues.set(index, object);
				index++;
				if (Space.isInSpace(SColors.SCALE_MS_SPACE, object)) {
					objectMark = SColors.scaleSpace.getColor(object);
					if(objectMark == 0) {
						this.numSavedDead++;
					}
				} 
			} else {
				if(lost == 0) {
					ScaleLogger.acquireLogLock();
					Log.prependThreadId();
					Log.write("saveObjectsFront - !!! no place to store helper's stack, index=");
					Log.write(index);
					Log.write(", size=");
					Log.writeln(size);
					Log.flush();
					ScaleLogger.releaseLogLock();
				}
				lost++;
			}
		}
		this.numSavedValues = index;
		this.done = true;
		if (Options.scaleDebug.getValue() > 5) {
			ScaleLogger.acquireLogLock();
			Log.prependThreadId();
			Log.write("saveObjectsFront - done storing helper's stack, numSavedValues=");
			Log.write(numSavedValues);
			Log.write(", numSavedDead=");
			Log.write(this.numSavedDead);
			Log.write(", lost=");
			Log.writeln(lost);
			Log.flush();
			ScaleLogger.releaseLogLock();
		}		
	}
	
	void setRoot(ObjectReference root) {
		this.root = root.toAddress();
	}

	int getIndex() {
		return this.index;
	}

	ObjectReference getColorMark() {
		return Address.fromIntSignExtend(index).toObjectReference();
	}
	
	boolean markLive() {
		if (live) {
			return false;
		}
		acquireColorsTableLock();	
		live = true;	
		releaseColorsTableLock();
		traceLiveColor(this.index);
				
		return true;
	}
	
	void addDependentColor(int otherColor) {
		if(otherColor < 0 || otherColor > colorsTableIndex) {
			ScaleLogger.acquireLogLock();
			Log.prependThreadId();
			Log.write("\t !!! Color.addDependentColor - bad otherColor=");
			Log.write(otherColor);
			Log.write(", index=");
			Log.writeln(index);
			Log.flush();
			ScaleLogger.releaseLogLock();
		}
		if(!this.otherColors[otherColor]) {
			if (Options.scaleDebug.getValue() > 5) {
				ScaleLogger.acquireLogLock();
				Log.prependThreadId();
				Log.write("\tColor.addDependentColor - adding dependence from ");
				Log.write(index);
				Log.write(" to ");
				Log.writeln(otherColor);
				Log.flush();
				ScaleLogger.releaseLogLock();
			}
			this.otherColors[otherColor] = true;
		}
	}

	boolean isLive() {
		return live;
	}
	
	boolean isDone() {
		return done;
	}
	
	void setDone() {
		done = true;
	}
	
	void addLive() {
		this.madeLive++;
	}

	long getLive() {
		return this.madeLive;
	}

	void addColored(int regColor) {
		this.colored++;
		//this is for self checking
		if(regColor == 1) {
			this.liveColored++;
		} else if(regColor == 2) {
			this.markedColored++;
		} else if(regColor == 0) {
			this.deadColored++;
		}
		if(this.colored == maxObjectsToColor) {
			if(Options.scaleDebug.getValue() > 5) {
				ScaleLogger.acquireLogLock();
				Log.prependThreadId();
				Log.write("\taddColored - num colored objects exceeded maximim for the first time, index=");
				Log.writeln(index);
				ScaleLogger.releaseLogLock();
			}
			done = true;
		}
	}
	
	void addOtherSpace(ObjectReference object) {
		//this is a because we do not color other space objects
		Space space = Space.getSpaceForObject(object);
		if(!space.isLive(object)) {
			return;
		}
		if(numOSObjects < SAVE_OTHER_SPACE) {
			this.osObjects.set(numOSObjects, object);
			this.numSavedOSObjects++;
		}
		this.numOSObjects++;
		markLive();
	}

	//TODO
	/*
	boolean hasColor(ObjectReference color) {
		return this.colors.hasColor(color);
	}*/

	public ObjectReferenceArray getSavedValues() {
		return this.savedValues;
	}

	public int getNumSavedValues() {
		return this.numSavedValues;
	}
	
	public void resetNumSavedValues() {
		this.numSavedValues = 0;
	}
	
	public void resetNumColored() {
		this.colored = 0;
	}

	public long getColored() {
		return this.colored;
	}

	public static int getColorTableTraces() {
		return colorTableTraces;
	}

	public boolean isSavedValuesTraced() {
		return this.savedValuesTraced;
	}
	public int getNumSavedOSObjects() {
		return this.numSavedOSObjects;
	}
	public ObjectReferenceArray getOsObjects() {
		return this.osObjects;
	}
	
	private int otherColors() {
		int result = 0;
		int end = getColorsTableEnd();
		for (int j = 1; j < end; j++) {
			if (j == this.index) {
				continue;
			}
			if (!this.otherColors[j]) {
				continue;
			}
			result++;
		}
		
		return result;
	}
	
}
